package com.suanfa;

import java.util.Arrays;
import java.util.HashMap;

public class Sort
{
    public static void main(String[] args)
    {
        int[] s = {12, 34, 23, 45, 30, 8};
        //交换排序
        maopao(s);
        //kuaisu(s,0,5);
        //插入排序
        //charu(s);
        //xier(s);
        //选择排序
        //zhijiexuanze(s);
        //dui(s);
        //----------
        //guibing(s);
        System.out.println(Arrays.toString(s));

    }

    /*************************************************/
    public static void maopao(int[] a)
    {
        int temp;
        // 做多少轮排序（最多length-1轮）
        for (int i = 0; i < a.length - 1; i++)
        {
            //优化，记录每次遍历是否发生过交换
            boolean change = false;
            // 每一轮比较多少次
            for (int j = 0; j < a.length - 1 - i; j++)
            {
                //如果前一个值大于后一个，则调整两者位置
                if (a[j] > a[j + 1])
                {
                    // 交换次序
                    temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                    change = true;
                }

            }
            //若无交换，说明排序成功
            if (!change) return;
        }

    }

    /*************************************************/
    public static void kuaisu(int[] a, int begin, int end)
    {
        if (a == null && a.length == 0)
        {
            return;
        }
        int left = begin, right = end;
        int p = a[left];//定义基准
        while (left < right)
        { //一趟遍历结束的条件
            // 从后往前遍历，找比p小的
            while (left < right && a[right] >= p)
            {
                //右指针左移
                right--;
            }
            //将查找到小的元素，赋给左指针（此时右指针元素多余）
            a[left] = a[right];
            //从前往后遍历，找比p大的
            while (left < right && a[left] <= p)
            {
                left++;
            }
            //将查找到大的元素，赋给右指针（此时左指针元素多余）
            a[right] = a[left];
            a[left] = p;
            //一轮排序后左右指针指向同一位置(中间)，且是p
        }

        //left-1>begin 说明此时左边分区的元素大于一个，要继续排。
        if (left - 1 > begin)
        {
            kuaisu(a, begin, left - 1);
        }
        //同理
        if (right + 1 < end)
        {
            kuaisu(a, right + 1, end);
        }

    }

    /*************************************************/
    public static void charu(int[] a)
    {
//	 for (int i = 1; i < a.length; i++)
//	 {
//         int j = i;
//         //记录当前待排元素的值
//         int temp = a[j];
//         while (j > 0 && a[j - 1] > temp)
//         {
//        	 //插入到第j位
//             a[j] = a[j - 1];
//             j = j - 1;
//         }
//         a[j] = temp;
//     }

        int p;
        for (int i = 1; i < a.length; i++)
        {
            //待排元素小于有序序列的最后一个元素时，向前插入
            if (a[i] < a[i - 1])
            {
                //记录当前待排元素的值
                p = a[i];
                //向前遍历有序序列
                for (int j = i; j >= 0; j--)
                {
                    if (j > 0 && a[j - 1] > p)
                    {
                        a[j] = a[j - 1];
                    }
                    else
                    {
                        a[j] = p;
                        break;
                    }
                }
            }
        }

    }

    /*************************************************/
    public static void xier(int[] a)
    {
        //增量每次都/2
        for (int step = a.length / 2; step > 0; step /= 2)
        {
            //从增量那组开始进行插入排序，直至完毕
            for (int i = step; i < a.length; i++)
            {
                int j = i;
                int temp = a[j];
                // j - step 就是代表与它同组隔壁的元素
                while (j - step >= 0 && a[j - step] > temp)
                {
                    a[j] = a[j - step];
                    j = j - step;
                }
                a[j] = temp;
            }
        }


    }


    /*************************************************/
    public static void zhijiexuanze(int[] a)
    {
        //从序列的第一个元素开始遍历
        for (int i = 0; i < a.length; i++)
        {
            //记录最小元素的下标
            int min = i;
            //在剩余序列中查找最小元素
            for (int j = i; j < a.length; j++)
            {
                //当查找到比当前值小的元素，用min记录其小标
                if (a[j] < a[min]) min = j;
            }

            //如果min不等于刚开始的值，说明在遍历过程中，有查到比起始值小的元素
            //否则，起始值就是剩余序列中的最小值，不用进行调整
            if (min != i)
            {
                int tmp = a[i];
                a[i] = a[min];
                a[min] = tmp;
            }


        }
    }


    /*************************************************/
    public static void dui(int[] a)
    {
        //1.构建大顶堆
        for (int i = a.length / 2 - 1; i >= 0; i--)
        {
            //从第一个非叶子结点从下至上，从右至左调整结构
            adjustHeap(a, i, a.length);
        }
        //2.调整堆结构+交换堆顶元素与末尾元素
        for (int j = a.length - 1; j > 0; j--)
        {
            swap(a, 0, j);//将堆顶元素与末尾元素进行交换
            adjustHeap(a, 0, j);//重新对堆进行调整
        }
    }

    /**
     * 调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上）
     *
     * @param arr
     * @param i
     * @param length
     */
    public static void adjustHeap(int[] arr, int i, int length)
    {
        int temp = arr[i];//先取出当前元素i
        for (int k = i * 2 + 1; k < length; k = k * 2 + 1)
        {//从i结点的左子结点开始，也就是2i+1处开始
            if (k + 1 < length && arr[k] < arr[k + 1])
            {//如果左子结点小于右子结点，k指向右子结点
                k++;
            }
            if (arr[k] > temp)
            {//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
                arr[i] = arr[k];
                i = k;
            }
            else
            {
                break;
            }
        }
        arr[i] = temp;//将temp值放到最终的位置
    }

    /**
     * 交换元素
     *
     * @param arr
     * @param a
     * @param b
     */
    public static void swap(int[] arr, int a, int b)
    {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }


    /*************************************************/
    public static void guibing(int[] arr)
    {
        sort(arr, 0, arr.length - 1);
    }


    public static void merge(int[] a, int L, int mid, int R)
    {
        int[] temp = new int[R - L + 1];
        int i = 0;
        int p1 = L;
        int p2 = mid + 1;
        // 比较左右两部分的元素，哪个小，把那个元素填入temp中
        while (p1 <= mid && p2 <= R)
        {
            temp[i++] = a[p1] < a[p2] ? a[p1++] : a[p2++];
        }
        // 上面的循环退出后，把剩余的元素依次填入到temp中
        // 以下两个while只有一个会执行
        while (p1 <= mid)
        {
            temp[i++] = a[p1++];
        }
        while (p2 <= R)
        {
            temp[i++] = a[p2++];
        }
        // 把最终的排序的结果复制给原数组
        for (i = 0; i < temp.length; i++)
        {
            a[L + i] = temp[i];
        }
    }


    public static void sort(int[] arr, int L, int R)
    {
        if (L == R)
        {
            return;
        }
        int mid = L + ((R - L) >> 1);
        sort(arr, L, mid);
        sort(arr, mid + 1, R);
        merge(arr, L, mid, R);
    }


}
